from typing import List


class DSU:
    def __init__(self, n: int):
        self._n = n
        self._array = [i for i in range(n)]
        self._size = [1] * n

    def find(self, i: int) -> int:
        if self._array[i] != i:
            self._array[i] = self.find(self._array[i])
        return self._array[i]

    def union(self, i: int, j: int) -> bool:
        i, j = self.find(i), self.find(j)
        if i != j:
            if self._size[i] >= self._size[j]:
                self._array[j] = i
                self._size[i] += self._size[j]
            else:
                self._array[i] = j
                self._size[j] += self._size[i]
            return True
        else:
            return False

    def is_connected(self, i: int, j: int) -> bool:
        return self.find(i) == self.find(j)

    @property
    def group_num(self):
        """计算连通分支数量"""
        return len(set(self._array))

    @property
    def max_group_size(self):
        """计算最大连通分支包含的数量"""
        import collections
        self._count_lazy()
        return max(collections.Counter(self._array).values())

    def _count_lazy(self):
        """将所有坐标指向根结点"""
        for i in range(self._n):
            self.find(i)


class PrimeFactorDecompositioner:
    """质因数分解计算器"""

    def __init__(self, size):
        """size=支持分解的最大数"""
        self.size = size
        self.primes = self.get_primes(int(pow(self.size, 0.5)) + 1)  # 计算需要的质因数列表

    def get_prime_factors(self, x):
        """计算x的质因数列表（如果同一个质因数有多个，则返回多个）"""
        res = []
        for prime in self.primes:
            if prime > x:
                break
            while x % prime == 0:
                res.append(prime)
                x //= prime
        if x > 1:
            res.append(x)
        return res

    @staticmethod
    def get_primes(n: int) -> list:
        if n < 2:
            return []

        num_list = [True] * n
        num_list[0], num_list[1] = False, False

        for i in range(2, int(pow(n, 0.5)) + 1):
            if num_list[i]:  # 如果i为质数(不是任何质数的倍数)
                num_list[i * i::i] = [False] * ((n - i * i - 1) // i + 1)  # 因为要包含i*i所以需要+1；因为n不在列表里，所以需要-1

        return [i for i in range(n) if num_list[i]]


class Solution:
    def largestComponentSize(self, nums: List[int]) -> int:
        size = len(nums)

        # 定义并查集
        dsu = DSU(size)

        # 定义质因数分解计算器
        prime_factor_decompositioner = PrimeFactorDecompositioner(10 ** 6)

        count = {}
        for i, num in enumerate(nums):
            factors = prime_factor_decompositioner.get_prime_factors(num)  # 分解质因子
            for factor in set(factors):
                if factor in count:  # 如果质因子已经出现过
                    dsu.union(i, count[factor])
                else:  # 如果质因子还没有出现过
                    count[factor] = i

        return dsu.max_group_size


if __name__ == "__main__":
    print(Solution().largestComponentSize([4, 6, 15, 35]))  # 4
    print(Solution().largestComponentSize([20, 50, 9, 63]))  # 2
    print(Solution().largestComponentSize([2, 3, 6, 7, 4, 12, 21, 39]))  # 8

    # 测试用例66/100 : 8
    print(Solution().largestComponentSize([99, 100, 69, 39, 14, 56, 91, 60]))
